package com.sheng.leetcode.year2022.month09.day17;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/09/19
 *<p>
 * 1624. 两个相同字符之间的最长子字符串<p>
 *<p>
 * 给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，<p>
 * 计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。<p>
 * 子字符串 是字符串中的一个连续字符序列。<p>
 *<p>
 * 示例 1：<p>
 * 输入：s = "aa"<p>
 * 输出：0<p>
 * 解释：最优的子字符串是两个 'a' 之间的空子字符串。<p>
 *<p>
 * 示例 2：<p>
 * 输入：s = "abca"<p>
 * 输出：2<p>
 * 解释：最优的子字符串是 "bc" 。<p>
 *<p>
 * 示例 3：<p>
 * 输入：s = "cbzxy"<p>
 * 输出：-1<p>
 * 解释：s 中不存在出现出现两次的字符，所以返回 -1 。<p>
 *<p>
 * 示例 4：<p>
 * 输入：s = "cabbac"<p>
 * 输出：4<p>
 * 解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。<p>
 *<p>
 * 提示：<p>
 *<p>
 * 1 <= s.length <= 300<p>
 * s 只含小写英文字母<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/largest-substring-between-two-equal-characters">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1624 {

    @Test
    public void test01() {
//        String s = "aa";
//        String s = "abca";
//        String s = "cbzxy";
        String s = "cabbac";
        System.out.println(new Solution().maxLengthBetweenEqualCharacters(s));
    }
}
class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int max = -1;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i + 1 == j) {
                        max = Math.max(0, max);
                    } else {
                        max = Math.max(s.substring(i + 1, j).length(), max);
                    }
                }
            }
        }
        int[] ints = new int[26];
        Arrays.fill(ints, -1);
        int maxLength = -1;
        for (int i = 0; i < length; i++) {
            if (ints[s.charAt(i) - 'a'] < 0) {
                ints[s.charAt(i) - 'a'] = i;
            } else {
                maxLength = Math.max(maxLength, i - ints[s.charAt(i) - 'a'] - 1);
            }
        }
        return max;
    }
}
